package library.algorithm;

import java.util.List;

public class BinaryInsert<Type> implements ArrayInsert<Type> {

	@Override
	public int insert(List<Type> in, Type t) {
     int lp, rp, mp;
     Comparable<Type> ltype;
     
     for(lp = 0, rp = in.size() - 1; lp <= rp;) {
       mp = (lp + rp) / 2;
       ltype = (Comparable<Type>)in.get(mp);
       if(ltype.compareTo(t) == 0)
        return mp;
       else if(ltype.compareTo(t) > 0)
        rp = mp - 1;
       else
        lp = mp + 1;
     }
     
     if(in.size() <= lp)
      return in.size();

     ltype = (Comparable<Type>)in.get(lp);
     if(ltype.compareTo(t) < 0 )
      return lp  + 1;
     
     return lp;
	}
}

